package MyUnionFind;

import java.util.Arrays;

/**
 * 684. 冗余连接
 *
 * 在本问题中, 树指的是一个连通且无环的无向图。
 *
 * 输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
 *
 * 结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
 *
 * 返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
 *
 * 示例 1：
 *
 * 输入: [[1,2], [1,3], [2,3]]
 * 输出: [2,3]
 * 解释: 给定的无向图为:
 *   1
 *  / \
 * 2 - 3
 */
public class Leetcode0684 {
    public static int[] findRedundantConnection(int[][] edges) {
        int nodeLen = edges.length;
        int[] parent = new int[nodeLen+1];
        for(int i=1; i<nodeLen+1; i++){
            parent[i] = i;
        }

        for(int i=0; i<nodeLen; i++){
            int[] tmp = edges[i];
            if(!isConnected(parent, tmp[0], tmp[1])){
                union(parent, tmp[0], tmp[1]);
            }else{
                return tmp;
            }
        }
        return new int[]{-1,-1};
    }

    /**
     * 查看元素所属于哪个集合
     *
     * @param element 要查看的元素
     * @return element元素所在的集合
     */
    private static int find(int[] parent, int element) {
        while (element != parent[element]) {
            //进行路径压缩
            parent[element] = parent[parent[element]];
            element = parent[element];
        }
        return element;
    }
    /**
     * 判断两个元素是否同属于一个集合
     *
     * @param firstElement  第一个元素
     * @param secondElement 第二个元素
     * @return <code>boolean</code> 如果是则返回true。
     */
    public static boolean isConnected (int[] parent, int firstElement, int secondElement) {
        return find(parent, firstElement) == find(parent, secondElement);
    }
    /**
     * 合并两个元素所在的集合，也就是连接两个元素
     *
     * @param firstElement  第一个元素
     * @param secondElement 第二个元素
     */
    public static void union (int[] parent, int firstElement, int secondElement) {
        int firstRoot = find(parent, firstElement);
        int secondRoot = find(parent, secondElement);
        if (firstRoot == secondRoot) {
            return;
        }
        parent[firstRoot] = secondRoot;
    }

    public static void main(String[] args) {
        int[][] edges = new int[][]{
                {1,2},{1,3},{1,4},{1,4},{2,5}
        };
        System.out.println(Arrays.toString(findRedundantConnection(edges)));
    }
}
